package com.tgy.链表;

import java.util.Stack;

/***
 * @ClassName: StackReverseLinkedList
 * @Description: 自己写反转单链表运用栈
 * @Auther: tanggy3
 * @Date: 20:48 2022/7/5
 * @version : V1.0
 */
public class StackReverseLinkedList {
    public static void main(String[] args) {
        StackTest stackTest = new StackTest();
        stackTest.add(new Node(1, "a"));
        stackTest.add(new Node(2, "b"));
        stackTest.add(new Node(3, "c"));
        stackTest.add(new Node(4, "d"));
        stackTest.show();
        System.out.println("遍历栈开始");
        showMe(reverse2(stackTest.getNode()));

    }

    public static Node reverse(Node inNode) {
        /**
         * 放入栈中
         */
        Stack<Node> stack = new Stack<Node>();
        Node temp = inNode;
        while (temp.nextNode != null) {
            stack.push(temp.nextNode);
            temp = temp.nextNode;
        }
        System.out.println("已经全部放入栈中");

        /**
         * 从栈中取出来
         */
        Node outNode = new Node();
        Node temp1 = outNode;
        while (!stack.isEmpty()) {
            Node stackNode = stack.pop();
            stackNode.nextNode = null;
            temp1.nextNode = stackNode;
            temp1 = stackNode;
        }
        return outNode;
    }


    /**
     * 复习使用栈反转单链表
     *
     * @param inNode
     * @return
     */
    public static Node reverse1(Node inNode) {
        if (inNode.nextNode == null) {
            System.out.println("链表为空");
        }
        //创建栈
        Stack<Node> stack = new Stack<>();
        //遍历原始node放入栈
        Node temp = inNode.nextNode;
        while (temp != null) {
            stack.push(temp);
            temp = temp.nextNode;
        }
        Node outNode = new Node();
        Node curNode = outNode;
        //取出栈中的元素
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            pop.nextNode = null;
            curNode.nextNode = pop;
            curNode = pop;
        }
        return outNode;
    }

    public static Node reverse2(Node inNode) {
        Stack<Node> stack = new Stack<>();
        Node temp = inNode;
        while (temp.nextNode != null) {
            stack.push(temp.nextNode);
            temp = temp.nextNode;
        }
        Node outNode = new Node();
        Node curNode = outNode;
        while (!stack.isEmpty()) {
            Node temp1 = stack.pop();
            temp1.nextNode = null;
            curNode.nextNode = temp1;
            curNode = temp1;
        }


        return outNode;
    }


    //展示链表
    public static void showMe(Node node) {
        Node temp = node;
        if (node.nextNode == null) {
            System.out.println("链表为空");
            return;
        }
        while (temp.nextNode != null) {
            System.out.println(temp.nextNode);
            temp = temp.nextNode;
        }
    }
}
